package com.algorithm.ch1.cjm.tree;

import com.algorithm.ch1.cjm.tree.model.TreeNode;

/**
 * 将有序数组转换为二叉搜索树
 * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 * <p>
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 * <p>
 * 示例:
 * <p>
 * 给定有序数组: [-10,-3,0,5,9],
 * <p>
 * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
 * <p>
 *     0
 *    / \
 *   -3  9
 *  /    /
 * -10  5
 */
public class SortedArrayToBST {

    /**
     * 第二版 二分法
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST1(int[] nums){

        return toBST(nums, 0, nums.length -1);
    }

    private TreeNode toBST(int[] nums, int start, int end){

        if(start > end){
            return null;
        }

        int middle = (start + end)/2;

        TreeNode treeNode = new TreeNode(nums[middle]);

        treeNode.left = toBST(nums, start, middle - 1);
        treeNode.right = toBST(nums,middle + 1 , end);

        return treeNode;
    }

    /**
     * 第一版
     * 这个思路很好啊。也是高度平衡二叉树啊。。为啥不通过啊。
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {

        int length = nums.length;

        if(length == 0) {
            return null;
        }

        int flag = length%2;
        int index = length/2;

        TreeNode leftRoot = null;
        TreeNode left = null;

        TreeNode rightRoot = null;
        TreeNode right = null;

        TreeNode root = new TreeNode(nums[index]);

        int i = 0;
        int j = length - 1;
        while (i < index && j > index){

            left = new TreeNode(nums[i]);
            left.left = leftRoot;
            leftRoot = left;

            right = new TreeNode(nums[j]);
            right.right = rightRoot;
            rightRoot = right;

            i++;
            j--;
        }

        if(flag == 0 && leftRoot != null){
            leftRoot.right = new TreeNode(nums[index -1]);
        }
        if(flag == 0 && length == 2){
            leftRoot = new TreeNode(nums[index -1]);
        }

        root.left = leftRoot;
        root.right = rightRoot;

        return root;
    }
}
